package everydayone.merge;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.ListIterator;

/**
 * @Date 2020/04/16
 * @author 王光浩
 * @Thinking 使用暴力法
 * @Analysis 时间复杂度O（n^2），空间复杂度O（n）
 */
public class MyMethodOne {
	public int[][] merge(int[][] intervals) {
		LinkedList<int[]> ret = new LinkedList<int[]>();
		//遍历所有区间，将相交的区间进行合并
		for(int[] area : intervals) {
			ListIterator<int[]> li = ret.listIterator();
			while(li.hasNext()) {
				int[] temp = li.next();
				//如果两个区域存在交集
				if(helper(temp,area)) {
					li.remove();
					area[0] = Math.min(area[0], temp[0]);
					area[1] = Math.max(area[1], temp[1]);
				}
			}
			ret.add(area);
		}
		//将 List 转为 数组
		int[][] res = new int[ret.size()][2];
		int index = 0;
		for(int[] temp:ret) {
			res[index++] = temp;
		}
		return res;
		
    }
	/**
	 * @ 判断 first 和 second 是否存在交集
	 * @param first
	 * @param second
	 * @return 如果存在则返回 true，否则返回 false
	 */
	private boolean helper(int[] first , int[] second) {
		return Math.max(first[0], second[0]) <= Math.min(first[1], second[1]);
	}
}
